public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null){
            return;
        }
        ListNode mid = findMid(head);
        ListNode node = reverse(mid.next);
        mid.next = null;
        merge(head, node);
    }
    public ListNode findMid(ListNode head){
        ListNode slow = head, fast = head;
        while (fast!= null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverse(ListNode head){
        ListNode prev = null, curr = head, next;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    public void merge(ListNode node1, ListNode node2){
        while (node1 != null && node2 != null) {
            ListNode temp1 = node1.next;
            ListNode temp2 = node2.next;

            node1.next = node2;
            node2.next = temp1;

            node1 = temp1;
            node2 = temp2;
        }
    }

}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
